package 差分Plus离散化;

import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Stream;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/1 22:23
 */
public class 线段的最大重合 {
    /*
    第八节 加强堆的内容:
    加强堆的内容
     */
    /*
     有点类似于  **美团笔试的  最大流星!** 那道题!
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int nums[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i][1] = sc.nextInt();
        }
        int[] ints = heapFunction(nums);
        System.out.println(ints[0] + " " + ints[1]);

    }
    /*
    任何一个 重合区域的左边界,一定是, 某个线段的左边界
    ,所以 根据上面的 定论:
    就可以 直接 枚举每个 线段左边界 重合的区域的个数,就可以了
    两种方法:
    ①糙 方法
    ② 堆方法
     */

    public int[] uglyFunction(int nums[][]) {
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                min = Math.min(min, nums[i][j]);
                max = Math.max(max, nums[i][j]);
            }
        }
        int ans = 0, count = 0;
        for (double index = min + 0.5; index <= max; index++) {
            int temp = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i][0] < index && nums[i][1] > index) {
                    temp++;
                }
            }
            ans = Math.max(ans, temp);
        }
        return new int[]{ans, count};
    }

    public static int[] heapFunction(int nums[][]) {
        // 按照开始时间进行一个排序
        Arrays.sort(nums, (a, b) -> {
            return a[0] - b[0];
        });
        // 准备一个小根堆
        /*
         堆里面存储的是每一个 线段区间的 et （结束时间）
         - 两个线段 x y
         现在 枚举 x(st)
         怎么判断 以 x(st) 开始的 重合区间个数  (注意 这里 是   以 x(st) 时间开头的重合 区域, 以 x(st) 这一点要非常的理解)
         如果 y(et) > x(st) 就说明有重合, 这里非常抽象, 建议画图理解
         */
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int ans = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!minHeap.isEmpty() && minHeap.peek() < nums[i][0]) {
                minHeap.poll();
            }
            minHeap.add(nums[i][1]);

            ans = Math.max(ans, minHeap.size());
//            if(ans == minHeap.size()){
//                count += minHeap.peek() - nums[i][0] + 1;
//            }else if(ans < minHeap.size()){
//                ans = minHeap.size();
//                count = minHeap.peek() - nums[i][0] + 1;
//            }
        }
        return new int[]{ans, count};
    }

    /*
      差分的 解法：
      把线段区间，看成是 diff 的 修改区间， 然后 在 求前缀和的过程中， 求出最大的前缀和！
      缺点 出来了，如果  集合的值域 很大的 话， 那么  差分数组 根本 就建立不起来！
     */
    public int difference(int nums[][]) {
        int max = 0;
        for (int num[] : nums) {
            max = Math.max(Arrays.stream(num).max().getAsInt(), max);
        }

//        int diff[] = new int[nums.length + 1];
        int diff[] = new int[max + 2];
        for (int i = 0; i < nums.length; i++) {
            diff[nums[i][0]] += 1;
            diff[nums[i][1] + 1] -= 1;
        }
        int sum = 0, ans = 0;
        for (int i = 0; i < diff.length - 1; i++) {
            sum += diff[i];
            ans = Math.max(ans, sum);
        }

        return ans;
    }


    @Test
    public void test() {
        int nums[][] = {{2, 6}, {1, 3}, {5, 7}};
        System.out.println(Arrays.toString(uglyFunction(nums)));
        System.out.println(Arrays.toString(heapFunction(nums)));
        System.out.println(difference(nums));
        System.out.println(diff(nums));
        System.out.println(diffDiscretization(nums));
    }


    // 关键是最大值的值域， 一般 值域的最小值， 很固定就是 0
    // 这种用数组的写法，只能适用于，值域不太大的题型
    public int diff(int nums[][]) {
        int min = nums[0][0], max = nums[0][0];
        for (int num[] : nums) {
            min = Math.min(min, num[0]);
            max = Math.max(max, num[1]);
        }
        int diff[] = new int[max + 2]; //  attention  is max +  2  这里 必须是 max + 2  这里注意一下 哈哈

        for (int num[] : nums) {
            diff[num[0]]++;
            diff[num[1] + 1]--;
        }
        int ans = 0, sum = 0;
        for (int i = 0; i < diff.length; i++) {
            sum += diff[i];
            ans = Math.max(ans, sum);
        }
        return ans;
    }

    /*
     离散化差分
     */
    public int diffDiscretization(int nums[][]) {
        int min, max;
        min = max = nums[0][0];
        // 离散化差分， 好像不用 求上面的信息
        TreeMap<Integer, Integer> diff = new TreeMap<>();

        for (int num[] : nums) {
            diff.put(num[0], diff.getOrDefault(num[0], 0) + 1);
            diff.put(num[1] + 1, diff.getOrDefault(num[0] + 1, 0) - 1);  // 别忘了 给 num + 1

        }
        int ans = 0, sum = 0;
        for (Map.Entry<Integer, Integer> entry : diff.entrySet()) {
            sum += entry.getValue();
            ans = Math.max(ans, sum);
        }

        return ans;
    }


    /*
     堆做法
     枚举 所有的 开头区间
     */
    public int solveHeap(int nums[][]) {

        Arrays.sort(nums, (a, b) -> a[0] - b[0]); // st 从小到达排序


        PriorityQueue<Integer> queue = new PriorityQueue<>(); // 只存储  et
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            while(!queue.isEmpty() &&  queue.peek() <= nums[i][0]){
                queue.remove(); // 弹出所有的不符合的 区间et
            }
            queue.add(nums[i][1]);
            ans = Math.max(queue.size(),ans);
        }
        return ans;
    }


}
